/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/sort-list
   @Language: C++
   @Datetime: 19-11-20 10:32
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
	ListNode* mergeList(ListNode *h1, ListNode *h2){
		ListNode *p, H(-1);
		for(p=&H; h1 && h2;){
			if(h1->val < h2->val){
				p=p->next=h1;
				h1=h1->next;
			}
			else{
				p=p->next=h2;
				h2=h2->next;
			}
		}
		p->next=(h1?h1:h2);
		return H.next;
	}
public:
	ListNode* sortList(ListNode* head) {
		if(!head || !(head->next)) return head;
		ListNode *p, H(-1);
		for(H.next=head, p=head=&H; p && p->next; head=head->next)
			p=p->next->next;
		p=head->next;
		head->next=NULL;
		return mergeList(sortList(H.next),sortList(p));
	}
};
